package gpl.pierrick.brihaye.util;

import java.util.Collection;
import java.util.Iterator;
import java.util.Set;
import java.util.Vector;

public class RangeSet implements Set<Integer> {
	/**A vector of ranges that in total defines tha whole range*/
	private Vector<Range> ranges = new Vector<Range>(); 
	
	/**Constructs an empty RangeSet*/
	public RangeSet() {}
	
	/***/
	public RangeSet(int from, int to) {
		ranges.add(new Range(from,to));
	}
	
	/**
	 * Returns number of integers stored in this set.
	 * @return number of integers stored.
	 */
	public int size() {
		int totalSize=0;
		for (int i=0; i<ranges.size();i++) {
			Range range = ranges.elementAt(i);
			totalSize += range.to - range.from + 1;
		}
		return totalSize;
	}

	/**
	 * Tells whether this set is empty or not.
	 * @return <code>true</code> if the set is empty
	 */
	public boolean isEmpty() {
		return ranges.isEmpty();
	}

	/**
	 * Check for an Integer or Character to exist in the set.
	 * An integer is in the set if lies in one of its ranges.
	 * For checking, we use a slightly modified version of binary search.
	 * @param x the integer to check in the set.
	 * If this parameter is not of type Integer or Character an IllegalArgumentException is thrown.
	 * @return true if this integer is found
	 * @throws IllegalArgumentException if the passed parameter is neither Integer nor Character
	 */
	public boolean contains(Object o) {
		//first, retrive the number passed
		Integer i = (Integer)o;
		int num = i.intValue();
		
		//second, check it in the set
		int l=0, h=ranges.size()-1, m=0;
		while (l <= h) {
			m = (l+h)>>1;
			Range r = ranges.elementAt(m);
			if (num >= r.from && num <= r.to)
				return true;
			if (num < r.from)
				h = m-1;
			else l = m+1;
		}
		return false;
	}

	public Iterator<Integer> iterator() {
		return new RangeSetItr();
	}

	public Object[] toArray() {
		return toArray(new Integer[size()]);
	}

	@SuppressWarnings("unchecked")
	public <T> T[] toArray(T[] arValues) {
		int i=0;
		for (Range range : ranges) {
			for (int j=range.from;j<=range.to;j++)
				arValues[i++] = (T)new Integer(j);
		}
		return arValues;
	}

	public boolean add(Integer c) {
		//first, retrive the number passed
		int num=0;
		num = c.intValue();
		
		//second, check it in the set
		int l=0, h=ranges.size()-1, m=0;
		Range r=null;
		while (l <= h) {
			m = (l+h)>>1;
			r = ranges.elementAt(m);
			if (num >= r.from && num <= r.to)
				return false;
			if (num < r.from)
				h = m-1;
			else l = m+1;
		}
		
		//third, see where to add the new number
		r = new Range(num,num);
		ranges.add(l,r);
		
		//fourth, check if we can merge the new range with its previous or next or both
		Range r2 = null;
		h = Math.min(l+1,ranges.size()-1);
		l = Math.max(l-1,0);
		while (l < h) {
			//try to merge l with l+1
			r = ranges.elementAt(l);
			r2 = ranges.elementAt(l+1);
			if (r.to == r2.from - 1) {
				r2.from = r.from;
				ranges.remove(l);
				h--;
			} else
				l++;
		}
		return true;
	}

	/**
	 * TODO remove an element from the set and split if necessary
	 */
	public boolean remove(Object arg0) {
		// TODO Auto-generated method stub
		return false;
	}

	/**
	 * Checks if all the Integers or Characters in the Collection are in the set or not.
	 * @param col
	 * @return <code>true</code> if all values in the Collection are in the set.
	 * @throws IllegalArgumentException if one of the values in the collection is not Integer or Character.
	 */
	public boolean containsAll(Collection<?> col) {
		Iterator<?> i = col.iterator();
		while (i.hasNext()) {
			if (!contains(i.next()))
				return false;
		}
		return true;
	}

	public boolean addAll(Collection<? extends Integer> col) {
		boolean changed = false;
		if (col.isEmpty())
			return changed;
		if (col instanceof RangeSet) {
			//a special (hopefully faster) algorithm for input of RangeSet
			RangeSet rs = (RangeSet)col;
			//check special case of empty set
			if (this.isEmpty()) {
				this.ranges = new Vector<Range>(rs.ranges);
				changed = true;
				return changed;
			}
			
			//an algorithm that is very similar to Merge
			int i1=0;
			int i2=0;
			Range r1=this.ranges.elementAt(i1);
			Range r1_1=null;
			Range r2=rs.ranges.elementAt(i2);
			while (r1!=null && r2!=null) {
				if (r1.to < r2.from + 1) {
					// if r1 is before r2 (no overlapping)
					
					//check if this may be merged with previous one
					if (r1_1 != null && r1.from <= r1_1.to+1) {
						//merge it with previous one
						r1_1.to = r1.to;
						this.ranges.remove(i1);
						r1 = i1 < this.ranges.size() ? this.ranges.elementAt(i1): null;
					} else {
						r1_1 = r1;
						// advance r1 by one
						r1 = ++i1 < this.ranges.size() ? this.ranges.elementAt(i1): null;
					}
				} else if (r1.from > r2.to + 1) {
					// if r1 is after r2 (no overlapping)
					//copy r2 to current range
					this.ranges.add(i1,(Range) r2.clone());
					r1 = r2;
					//advance r2 by one
					r2 = ++i2 < rs.ranges.size() ? rs.ranges.elementAt(i2): null;
				} else {
					//they are overlapping
					//add r2 to r1
					if (r2.from < r1.from)
						r1.from = r2.from;
					if (r2.to > r1.to)
						r1.to = r2.to;
					//advance r2 by one
					r2 = ++i2 < rs.ranges.size() ? rs.ranges.elementAt(i2): null;
				}
			}
			//copy the rest of the source
			while (r1 != null){
				//check if this may be merged with previous one
				if (r1_1 != null && r1.from <= r1_1.to+1) {
					//merge it with previous one
					r1_1.to = r1.to;
					this.ranges.remove(i1);
					r1 = i1 < this.ranges.size() ? this.ranges.elementAt(i1): null;
				} else {
					r1_1 = r1;
					// advance r1 by one
					r1 = ++i1 < this.ranges.size() ? this.ranges.elementAt(i1): null;
				}
			}
			//copy the rest to the destination
			while (r2 != null) {
				if (r1_1.to < r2.from + 1) {
					// if r1 is before r2 (no overlapping)
					//copy r2 to current range
					this.ranges.add(i1++,(Range) r2.clone());
					r1_1 = r2;
				} else {
					//they are overlapping
					//add r2 to r1
					if (r2.from < r1_1.from)
						r1_1.from = r2.from;
					if (r2.to > r1_1.to)
						r1_1.to = r2.to;
				}
				// advance r2 by one
				r2 = ++i2 < rs.ranges.size() ? rs.ranges.elementAt(i2): null;
			}
		} else {
			for (Integer i : col) {
				add(i);
				changed=true;
			}
		}
		return changed;
	}

	/**
	 * TODO remove all elements except those in the Collection.
	 * @param arg0
	 * @return
	 */
	public boolean retainAll(Collection<?> arg0) {
		// TODO Auto-generated method stub
		return false;
	}

	/**
	 * TODO remove all elements in the Collection.
	 * @param arg0
	 * @return
	 */
	public boolean removeAll(Collection<?> arg0) {
		// TODO Auto-generated method stub
		return false;
	}

	/**
	 * Removes all elements in the set.
	 */
	public void clear() {
		ranges.clear();
	}
	
	@Override
	public String toString() {
		String str="";
		for (Range r : this.ranges)
			str += r;
		return str;
	}

	/**
	 * Iterator for the RangeSet
	 * @author Ahmed Saad
	 */
	class RangeSetItr implements Iterator<Integer>{
		/**Iterator for the next range to be visited*/
		private Iterator<Range> iRange = RangeSet.this.ranges.iterator();
		/**Holds the current range being visited*/
		private Range currentRange;
		/**Holds the current value being visited*/
		int value;
		
		public RangeSetItr() {}
		
		public boolean hasNext() {
			return iRange.hasNext() || (currentRange!=null && value<currentRange.to);
		}

		public Integer next() {
			if (!hasNext())
				return null;
			if ((currentRange==null || currentRange!=null && value>=currentRange.to) && iRange.hasNext()) {
				currentRange = iRange.next();
				value = currentRange.from;
			} else
				++value;
			return value;
		}

		public void remove() {
			throw new UnsupportedOperationException();
		}
	}
	
	public static void main(String[] args) {
		Set<Integer> r = new RangeSet();
		r.add(5);
		r.add(20);
		r.add(22);
		Set<Integer> r2 = new RangeSet(1,20);
		r2.add(50);
		r2.add(55);
		r2.add(51);
		r.addAll(r2);
		System.out.println(r);
	}

}

/**
 * Holds a range for the RangeSet
 * @author Ahmed Saad
 */
class Range {
	public int from,to;
	public Range(int from, int to) {
		this.from = from;
		this.to = to;
	}
	@Override
	public String toString() {
		return "["+this.from+"-"+this.to+"]";
	}
	@Override
	protected Object clone() {
		return new Range(this.from,this.to);
	}
	
}
